#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#include <string.h>
//
//class Solution {
//public:
//    int hash[100001];
//    int lower_bound(vector<int>& nums,int right,int t)
//    {
//        int l = 0, r = right;
//        while(l <= r)
//        {
//            int mid = l + (r-l) / 2;
//            if (nums[mid] < t && hash[mid] == 0) l = mid + 1;
//            else r = mid - 1;
//        }
//        return l;
//    }
//    int maxNumOfMarkedIndices(vector<int>& nums) {
//        if (nums.size() == 1) return 0;
//        sort(nums.begin(),nums.end());
//        for (auto& e : nums) cout << e << " ";
//        cout << endl;
//        memset(hash,0,sizeof(hash));
//        int ans = 0;
//        int cnt = 0;
//        int i = 0, n = nums.size();
//        for (i = n-2; i >= 0; i--)
//        {
//            if (!hash[i])
//            {
//                int ret = lower_bound(nums,i,(nums[i+1]/2)+1)-1;
//                if (ret != -1 && !hash[ret])
//                {
//                    ++cnt;
//                    ans += 2;
//                hash[ret]++;
//                }
//            }
//
//        }
//    cout << "cnt->" << cnt << endl;
//        return ans;
//    }
//};
//
//
//int main()
//{
//    Solution _s;
//    vector<int> nums = {42,83,48,10,24,55,9,100,10,17,17,99,51,32,16,98,99,31,28,68,71,14,64,29,15,40};
//    int ret = _s.maxNumOfMarkedIndices(nums);
//    cout << ret << endl;
//    return 0;
//}
//

class Solution {
public:
    bool check(vector<int>& weights,int t,int w)
    {
        int days = 0, tmp = 0;
        int i  = 0;

        while(i < weights.size())
        {
            //表示承载连其中一天的都承载不了，那就不行
            if (weights[i] > w) return true;
            if (tmp + weights[i] > w)
            {
                days++;
                tmp = 0;
                continue;
            }
            tmp += weights[i++];
        }
        return days > t;
    }
    int shipWithinDays(vector<int>& weights, int days) {
        int s = 0;
        for (auto& e : weights) s += e;
        //二分船的运载量
        int mx = 0;
        for (auto& e : weights) mx = max(e,mx); 
        int l = mx, r = s;
        while(l <= r)
        {
            int mid = l + (r-l) / 2;
            //如果所需要的天数 > days，说明承载太小了。
            if (check(weights,days,mid)) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
};

int main()
{
    vector<int> weights = {1,2,3,4,5,6,7,8,9,10};
    int days = 5;
    cout << Solution().shipWithinDays(weights,days) << endl;
    return 0;
}










